class Solution {
public:

    int dp[4] = { 0 };
    int tribonacci(int n)
    {
        if (n == 0)return 0;
        if (n == 1 || n == 2)return 1;
        dp[0] = 0, dp[1] = 1, dp[2] = 1;
        n -= 2;
        while (n--)
        {
            dp[3] = dp[0] + dp[1] + dp[2];
            dp[0] = dp[1], dp[1] = dp[2], dp[2] = dp[3];
        }
        return dp[3];


    }
};